两道题的转移式是一样的,只是优化不同。
令 为完成前 个任务的最小花费。
你会发现每次操作后总时间会增加 ,这样就不好处理当前时间。
所以可以用前几周讲到的方法,将 的贡献提前计算,那么有转移
将与 无关的提到外面来
我们只需要求出 的最小值即可。
P2365
假设有两个决策点 ,且 比 优。
那么有:
这里变号是因为
然后就可以斜率优化了。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN = 3e5;
int n , s , T[ MAXN + 5 ] , C[ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
LL dp[ MAXN + 5 ];
LL fx( int i ) { return C[ i ]; }
LL fy( int i ) { return dp[ i ] - s * C[ i ]; }
double Slope( int i , int j ) {
return ( fy( i ) - fy( j ) ) * 1.0 / ( fx( i ) - fx( j ) );
}
int main( ) {
scanf("%d %d",&n,&s);
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d %d",&T[ i ],&C[ i ]);
T[ i ] += T[ i - 1 ] , C[ i ] += C[ i - 1 ];
}
Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
for( int i = 1 ; i <= n ; i ++ ) {
for( ; Head + 1 <= Tail && Slope( Que[ Head ] , Que[ Head + 1 ] ) <= T[ i ] ; Head ++ );
dp[ i ] = dp[ Que[ Head ] ] + 1ll * ( C[ i ] - C[ Que[ Head ] ] ) * T[ i ] + s * ( C[ n ] - C[ Que[ Head ] ] );
for( ; Head + 1 <= Tail && Slope( Que[ Tail - 1 ] , Que[ Tail ] ) > Slope( Que[ Tail ] , i ) ; Tail -- );
Que[ ++ Tail ] = i;
}
printf("%lld\n", dp[ n ] );
return 0;
}
P5785
这道题看起来和上一道一样,但是 可以为负数。
这就意味着 不一定递增,不能直接删掉斜率不大于 的点。
但是仍然可以维护一个斜率递增的队列,在里面二分就可以了。
这道题卡精度,不要用除法。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define LL long long
const int MAXN = 3e5;
int n , s , T[ MAXN + 5 ] , C[ MAXN + 5 ];
int Que[ MAXN + 5 ] , Head , Tail;
LL dp[ MAXN + 5 ];
LL fx( int i ) { return C[ i ]; }
LL fy( int i ) { return dp[ i ] - 1ll * s * C[ i ]; }
signed main( ) {
scanf("%d %d",&n,&s);
for( int i = 1 ; i <= n ; i ++ ) {
scanf("%d %d",&T[ i ],&C[ i ]);
T[ i ] += T[ i - 1 ] , C[ i ] += C[ i - 1 ];
}
Head = 1 , Tail = 0; Que[ ++ Tail ] = 0;
for( int i = 1 , opt = 0 ; i <= n ; i ++ ) {
for( int l = Head , r = Tail ; l <= r ; ) {
int Mid = ( l + r ) >> 1;
if( Mid != Tail && ( fy( Que[ Mid ] ) - fy( Que[ Mid + 1 ] ) ) >= T[ i ] * ( fx( Que[ Mid ] ) - fx( Que[ Mid + 1 ] ) ) ) l = Mid + 1;
else r = Mid - 1 , opt = Que[ Mid ];
}
dp[ i ] = dp[ opt ] + 1ll * ( C[ i ] - C[ opt ] ) * T[ i ] + 1ll * s * ( C[ n ] - C[ opt ] );
for( ; Head + 1 <= Tail && ( fy( Que[ Tail - 1 ] ) - fy( Que[ Tail ] ) ) * ( fx( Que[ Tail ] ) - fx( i ) ) >= ( ( fy( Que[ Tail ] ) - fy( i ) ) ) * ( fx( Que[ Tail - 1 ] ) - fx( Que[ Tail ] ) ) ; Tail -- );
Que[ ++ Tail ] = i;
}
printf("%lld\n", dp[ n ] );
return 0;
}